翻訳と辞書 Words near each other ・ Branching order of bacterial phyla (Cavalier-Smith, 2002) ・ Branching order of bacterial phyla (Ciccarelli et al., 2006) ・ Branching order of bacterial phyla (Gupta, 2001) ・ Branching order of bacterial phyla (Rappe and Giovanoni, 2003) ・ Branching order of bacterial phyla (Woese, 1987) ・ Branching Out ・ Brancepeth Castle ・ Brancepeth, Saskatchewan ・ Branch ・ Branch (banking) ・ Branch (computer science) ・ Branch (disambiguation) ・ Branch (hieroglyph) ・ Branch (surname) ・ Branch and bound ・ Branch and cut ・ Branch and price ・ Branch Area Career Center ・ Branch attachment ・ Branch Avenue ・ Branch Avenue station ・ Branch Back Brook ・ Branch Banking (Wilson, North Carolina) ・ Branch Barrett Rickey ・ Branch Bocock ・ Branch Bragg ・ Branch Brook Park ・ Branch Brook Park (NLR station) ・ Branch Building ・ Branch Canyon Formation Dictionary Lists mini英和辞書 mini和英辞書 Webster 1913 Latin-English FOLDOC Wikipedia English ウィキペディア

翻訳と辞書　辞書検索 [ 開発暫定版 ] スポンサード リンク Branch and cut ： ウィキペディア英語版 Branch and cut Branch and cut is a method of combinatorial optimization for solving integer linear programs (ILPs), that is, linear programming (LP) problems where some or all the unknowns are restricted to integer values. Branch and cut involves running a branch and bound algorithm and using cutting planes to tighten the linear programming relaxations. Note that if cuts are only used to tighten the initial LP relaxation, the algorithm is called cut and branch. ==Description of the Algorithm== This description assumes the ILP is a maximization problem. The method solves the linear program without the integer constraint using the regular simplex algorithm. When an optimal solution is obtained, and this solution has a non-integer value for a variable that is supposed to be integer, a cutting plane algorithm may be used to find further linear constraints which are satisfied by all feasible integer points but violated by the current fractional solution. These inequalities may be added to the linear program, such that resolving it will yield a different solution which is hopefully "less fractional". At this point, the branch and bound part of the algorithm is started. The problem is split into multiple (usually two) versions. The new linear programs are then solved using the simplex method and the process repeats. During the branch and bound process, non-integral solutions to LP relaxations serve as upper bounds and integral solutions serve as lower bounds. A node can be pruned if an upper bound is lower than an existing lower bound. Further, when solving the LP relaxations, additional cutting planes may be generated, which may be either ''global cuts'', i.e., valid for all feasible integer solutions, or ''local cuts'', meaning that they are satisfied by all solutions fulfilling the side constraints from the currently considered branch and bound subtree. The algorithm is summarized below. #Add the initial ILP to $L$, the list of active problems #Set $x^$ * = \text and $v^$ * = -\infty #while the $L$ is not empty ##Select and remove a problem from $L$ ##Solve the LP relaxation of the problem. ##If the solution is infeasible, go back to 3 (while). Otherwise denote the solution by $x$ with objective value $v$. ##If $v\backslash le\; v^$ *, go back to 3. ##If $x$ is integer, set $v^$ *\leftarrow v, x^ * \leftarrow x and go back to 3. ##If desired, search for cutting planes that are violated by $x$. If any are found, add them to the LP relaxation and return to 3.2. ##Branch to partition the problem into new problems with restricted feasible regions. Add these problem to $L$ and go back to 3 #return $x^$ * 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「Branch and cut」の詳細全文を読む スポンサード リンク 翻訳と辞書 : 翻訳のためのインターネットリソース Copyright(C) kotoba.ne.jp 1997-2016. All Rights Reserved.